package leetcode.leetcode_hot100;

import java.util.HashSet;
import java.util.List;

/**
 * @ClassName T0139
 * @Description 单词拆分
 * @Author Fanxc
 * @DATE 2021/6/19 20:41
 * @Version 1.0
 */
public class T0139 {
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            HashSet<String> set=new HashSet<>(wordDict);
            int len=s.length();
            boolean[] dp=new boolean[len+1];
            dp[0]=true;

            //找到set中最长单词的长度
            int maxw=0;
            for(String c:set){
                maxw=Math.max(maxw,c.length());
            }

            for(int i=1;i<=len;i++){
                for(int j=i-1;j>=0&&maxw>=i-j;j--){
                    if(dp[j]&&set.contains(s.substring(j,i))){
                        dp[i]=true;
                        break;
                    }
                }
            }
            return dp[len];
        }
    }
}
